package 剑指offer;

import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:38:58 
* @Description：
* 
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
并保证奇数和奇数，偶数和偶数之间的相对位置不变。
*/
public class A13调整数组顺序使得奇数位于偶数前面 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int size = scanner.nextInt();
		int [] arr =new int [size];
		for (int i = 0; i < arr.length; i++) {
			arr[i]=scanner.nextInt();
		}
		//reOrderArray(arr);
		//adjust(arr);
		adjust1(arr);
		for (int i : arr) {
			System.out.print(i+" ");
		}
		
	}

	 public  static void reOrderArray(int [] array) {

		int num = array.length;
		for (int i = 0; i < num; i++)// 找到第一个偶数位置
		{
			if ((array[i] % 2) == 0) {            //偶数
				for (int j = i; j < num; j++) {
					if ((array[j] % 2) == 1)// 找到偶数后第一个奇数位置，从第一个偶数位开始后移
					{
					   int	temp = array[j];
						while (j > i) {
							array[j] = array[j - 1];// 将第一个偶数位开始后移
							j--;
						}
						array[j] = temp;// 将该奇数前移到第一个偶数位
						i++;// 第一个偶数位置后移一次
					}
				}
				break;
			}
		}
	}
	 
	 
	 
	 //类似于冒泡算法，前偶后奇就进行交换
	 public static void adjust(int [] arr) {
		 int len = arr.length;
			 for (int i = 0; i < arr.length; i++) {
					//因为是要求前面为奇数后面为偶数
				 //所以说，前偶后奇就进行交换
				 for(int j=len-1;j>i;j--) {
					 if (arr[j]%2==1 && arr[j-1]%2==0) {       //前偶后奇交换
						int temp=arr[j];
						arr[j]=arr[j-1];
						arr[j-1]=temp;
					}
				}
		}
	 }
	 
	 
	 //创建一个新的数组来保存结果
	 //新建一个数组先把原数组中的奇数push进去再把偶数push进去，然后用新数组数据覆盖原数组即可
	// 复杂度O(n)
	 
	 
	 /*
	  * a.遍历原数组，判断arr[i]是奇数还是偶数；如果为奇数，还是从原数组的头部开始插入，并记录下zhizhen
	  * b.如果是偶数，就放到新开辟的临时数组当中
	  * c.当数组全部遍历结束，奇数的任然在原先数组当中，偶数的都在临时数组当中，
	  *   现在只需要把临时数组当中的偶数在原数组的最后一个奇数后面全部插入进去即可
	  */
	 public static void adjust1(int [] arr) {
		 if (arr!=null) {
			int  [] temp=new int[arr.length];
			int jishuIndex=0;
			int oushuIndex=0;
			for (int i : arr) {
				if ((i&1)==1) {        //说明这个是奇数
					arr[jishuIndex++]=i;
				}
				else {
					temp[oushuIndex++]=i;      
				}
			}
		//把临时数组当中的所有偶数追加到原先数组中的奇数后面	
			for(int i=0;i<oushuIndex;i++) {
				arr[jishuIndex+i]=temp[i];
			}
		}
	 }
}
	    
